/*
148. 排序链表

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

示例 1：

输入：head = [4,2,1,3]
输出：[1,2,3,4]

示例 2：

输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]

示例 3：

输入：head = []
输出：[]
*/

class Solution {
    public ListNode sortList(ListNode head) {
        List<ListNode> list = new ArrayList<>();

        while (head != null) {
            list.add(head);
            head = head.next;
        }

        list.sort(Comparator.comparingInt(o -> o.val));

        ListNode newNode = new ListNode(-1);
        ListNode tem = newNode;

        for (ListNode listNode : list) {
            tem.next = listNode;
            tem = tem.next;
        }

        tem.next = null;

        return newNode.next;
    }
}